// 给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。
// 找到并返回可以用这种方式转换的最短回文串。

// 暴露接口
function shortestPalindrome(s: string): string {
    let reverseS: string = s.split('').reverse().join('');// 转置后的字符串
    let len: number = reverseS.length;
    // index初始化为字符串长度，最理想的情况当然是整个字符串都是回文串，那整个字符串就不用裁剪
    let sliceIndex: number = len;
    while (sliceIndex > 0) {
        // 找内部的最长回文串
        if (s.slice(0, sliceIndex) === reverseS.slice(len - sliceIndex, len)) {
            break;
        }
        sliceIndex--;
    }
    return reverseS.slice(0, len - sliceIndex) + s;
};


// 这道回文串的题目属于书写起来难度小但是思路并不太好想的一道题目
// 建议结合着草稿纸来配合思路的理解
// 首先入手这道题目需要先思考一些破解穷举的算法，思考字符串例如 aaab
// 其中这个aaa是一个回文串，这个aaa本身就是回文的，所以我们可以直接裁去这个aaa，剩下b
// 把b补在开头形成baaab就形成了最短字符串，同理可以思考 aacb的最短回文串是 bcaacb
// abadef的最短回文串是 fed aba def...多写几个其实可以找到规律，这道题目的核心点其实在于
// 我们需要找到以必须以首项索引作为起点的最长回文串，然后截取这个部分，把剩余部分逆置返回即可得到结果
// 写到这里其实可以有一个直白的思路出来，那就是先找回文串，再拼接
// 具体实现的操作上就可以将原字符串逆置，然后确定一个索引index，
// 原字符串从（0,index），转置字符串从（index，len）开始找回文串，
// 找到了回文串后只需要对转置的字符串从（0，len-index）裁剪拼回原字符串的头部，得到的结果就是最短回文串